// Copyright (c) 2011 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// Derived from google3/util/gtl/stl_util.h

#ifndef BASE_STL_UTIL_H_
#define BASE_STL_UTIL_H_

#include <algorithm>
#include <functional>
#include <iterator>
#include <string>
#include <vector>

#include "base/logging.h"

namespace base {

// Clears internal memory of an STL object.
// STL clear()/reserve(0) does not always free internal memory allocated
// This function uses swap/destructor to ensure the internal memory is freed.
template <class T>
void STLClearObject(T* obj)
{
    T tmp;
    tmp.swap(*obj);
    // Sometimes "T tmp" allocates objects with memory (arena implementation?).
    // Hence using additional reserve(0) even if it doesn't always work.
    obj->reserve(0);
}

// Counts the number of instances of val in a container.
template <typename Container, typename T>
typename std::iterator_traits<
    typename Container::const_iterator>::difference_type
STLCount(const Container& container, const T& val)
{
    return std::count(container.begin(), container.end(), val);
}

// Return a mutable char* pointing to a string's internal buffer,
// which may not be null-terminated. Writing through this pointer will
// modify the string.
//
// string_as_array(&str)[i] is valid for 0 <= i < str.size() until the
// next call to a string method that invalidates iterators.
//
// As of 2006-04, there is no standard-blessed way of getting a
// mutable reference to a string's internal buffer. However, issue 530
// (http://www.open-std.org/JTC1/SC22/WG21/docs/lwg-active.html#530)
// proposes this as the method. According to Matt Austern, this should
// already work on all current implementations.
inline char* string_as_array(std::string* str)
{
    // DO NOT USE const_cast<char*>(str->data())
    return str->empty() ? NULL : &*str->begin();
}

// Test to see if a set, map, hash_set or hash_map contains a particular key.
// Returns true if the key is in the collection.
template <typename Collection, typename Key>
bool ContainsKey(const Collection& collection, const Key& key)
{
    return collection.find(key) != collection.end();
}

// Test to see if a collection like a vector contains a particular value.
// Returns true if the value is in the collection.
template <typename Collection, typename Value>
bool ContainsValue(const Collection& collection, const Value& value)
{
    return std::find(collection.begin(), collection.end(), value) != collection.end();
}

// Returns true if the container is sorted.
template <typename Container>
bool STLIsSorted(const Container& cont)
{
    // Note: Use reverse iterator on container to ensure we only require
    // value_type to implement operator<.
    return std::adjacent_find(cont.rbegin(), cont.rend(),
               std::less<typename Container::value_type>())
        == cont.rend();
}

// Returns a new ResultType containing the difference of two sorted containers.
template <typename ResultType, typename Arg1, typename Arg2>
ResultType STLSetDifference(const Arg1& a1, const Arg2& a2)
{
    DCHECK(STLIsSorted(a1));
    DCHECK(STLIsSorted(a2));
    ResultType difference;
    std::set_difference(a1.begin(), a1.end(),
        a2.begin(), a2.end(),
        std::inserter(difference, difference.end()));
    return difference;
}

// Returns a new ResultType containing the union of two sorted containers.
template <typename ResultType, typename Arg1, typename Arg2>
ResultType STLSetUnion(const Arg1& a1, const Arg2& a2)
{
    DCHECK(STLIsSorted(a1));
    DCHECK(STLIsSorted(a2));
    ResultType result;
    std::set_union(a1.begin(), a1.end(),
        a2.begin(), a2.end(),
        std::inserter(result, result.end()));
    return result;
}

// Returns a new ResultType containing the intersection of two sorted
// containers.
template <typename ResultType, typename Arg1, typename Arg2>
ResultType STLSetIntersection(const Arg1& a1, const Arg2& a2)
{
    DCHECK(STLIsSorted(a1));
    DCHECK(STLIsSorted(a2));
    ResultType result;
    std::set_intersection(a1.begin(), a1.end(),
        a2.begin(), a2.end(),
        std::inserter(result, result.end()));
    return result;
}

// Returns true if the sorted container |a1| contains all elements of the sorted
// container |a2|.
template <typename Arg1, typename Arg2>
bool STLIncludes(const Arg1& a1, const Arg2& a2)
{
    DCHECK(STLIsSorted(a1));
    DCHECK(STLIsSorted(a2));
    return std::includes(a1.begin(), a1.end(),
        a2.begin(), a2.end());
}

} // namespace base

#endif // BASE_STL_UTIL_H_
